/**
 * 
 */
package leetCode;

import java.util.Stack;

/**
 * @author zhong
 *
 */
public class MaxChunksToMakeSortedII {
	public int maxChunksToSortedStack(int[] arr) {
		int n = arr.length;
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < n; i++) {
			int min = arr[i];
			while (!stack.isEmpty() && arr[i] < stack.peek()) {
				min = stack.pop();
			}
			stack.push(min);
		}
		return stack.size();
	}

	public int maxChunksToSorted(int[] arr) {
		int n = arr.length;
		int[] left = new int[n];
		int[] right = new int[n];
		for (int i = 1; i < right.length; i++) {
			left[i] = Math.max(left[i - 1], arr[i - 1]);
		}

		right[n - 1] = arr[n - 1];
		for (int i = n - 2; i >= 0; i--) {
			right[i] = Math.min(right[i + 1], arr[i]);
		}

		int res = 1;
		for (int i = 1; i < right.length; i++) {
			if (left[i] <= right[i]) {
				res++;
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = { 5, 1, 1, 8, 1, 6, 5, 9, 7, 8 };
		// 2,1,3,4,4
		// 1, 0, 1, 3, 2
		// 5,4,3,2,1
		// 1, 0, 1, 2, 1
		// 0,2,1,4,3
		// 5,1,1,8,1,6,5,9,7,8
		System.out.println(new MaxChunksToMakeSortedII().maxChunksToSorted(arr));
		System.out.println(new MaxChunksToMakeSortedII().maxChunksToSortedStack(arr));
	}

}
